package com.labuladong;

import java.util.Arrays;

/**
 * 项目名称: java_algorithm
 * @ClassName MakeChange
 * @Description 凑零钱算法
 * @Author huipanxing huipanxing@chinasofti.com   @Date 2022/6/10 14:09
 */
public class MakeChange {

    private static Integer EIGHT_EIGHT_EIGHT = -888;

    public static void main(String[] args) {
//        int[] array = new int[]{1, 2, 3};
//        int amount = 30;
//        int dp = dp(array, amount);
//        System.out.println(dp);

//        int[] array = new int[]{1, 2, 3};
//        int amount = 1000;
//        int[] memo = new int[amount + 1];
//        Arrays.fill(memo, EIGHT_EIGHT_EIGHT);
//        int dp = dp1(array, amount, memo);
//        System.out.println(dp);

        int[] array = new int[]{3, 3, 3};
        int amount = 100;
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, amount+1);
        memo[0]=0;
        int dp = dp2(array, amount, memo);
        System.out.println(dp);
    }

    /**
     * 简单暴力解法
     */
    public static int dp(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            //计算子问题结果
            int subDp = dp(coins, amount - coin);
            //如果子问题没有结果则跳过
            if (subDp == -1) {
                continue;
            }
            //在子问题中选择最优个数解
            res = Math.min(res, subDp + 1);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    /**
     * 带备忘录解法（自顶向下）
     */
    public static int dp1(int[] coins, int amount, int[] memo) {
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        if (memo[amount] != EIGHT_EIGHT_EIGHT) {
            return memo[amount];
        }
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            //计算子问题结果
            int subDp = dp1(coins, amount - coin, memo);
            //如果子问题没有结果则跳过
            if (subDp == -1) {
                continue;
            }
            //在子问题中选择最优个数解
            res = Math.min(res, subDp + 1);
        }
        memo[amount] = res == Integer.MAX_VALUE ? -1 : res;
        return memo[amount];
    }

    /**
     * dp数组动态规划解法(自底向上)
     */
    public static int dp2(int[] coins, int amount, int[] memo) {
        for (int i = 0; i < memo.length; i++) {
            for (int coin : coins) {
                if (i-coin<0){
                    continue;
                }
                memo[i]=Math.min(memo[i],1+memo[i-coin]);
            }
        }
        return memo[amount]==amount+1?-1:memo[amount];
    }
}
